# https://blog.csdn.net/weixin_42563968/article/details/113827000
# https://blog.csdn.net/lmp5023/article/details/115491119
# 数组：
    # 1、数组存储的数据在地址空间上是连续的。
    # 2、方便数据的查找，查找数据的时间复杂度为O(1）。

# 链表
    # 1、链表存储的数据在地址空间上可连续，可不连续。
    # 2、链表中的每一个节点都包括数据和指向下一个地址的指针。
    # 3、查找数据的时间复杂度为O(n)，方便数据的增删。
# 在链表中查找第 n 个数据以及查找指定的数据的时间复杂度是 O(N) ，但是插入和删除数据的时间复杂度是 O(1) ，因为只需要调整指针就可以。

# 栈
# 栈是一种先入后出的逻辑结构，每次加入新的元素和拿走元素都在顶部操作。
# 一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。
# 栈的基本操作：进栈（压栈）：push 、出栈：pop 、取栈顶：gettop

# 队列
# 队列是一种先入先出的逻辑结构，对元素的操作分别在对头和队尾，元素的插入在队尾，元素的删除在队头。
# 对队列的三个操作时间复杂度都是常量O(1)。
# 进队：append 、出队：popleft

# 二叉树：
# 每个节点至多只有两个子树的结构，在父节点中有指向左右子树的指针
# 先序遍历：根–左–右
# 中序遍历：左–根–右
# 后序遍历：左–右–根
# 查找二叉树：左子树的值小于根节点的值，右子树的值大于根节点的值，在插入数据时，从根节点开始往下比较，小于比较值则放在左边，大于比较值放在右边。插入一个值的时间复杂度是O(logn)
# 平衡二叉树：左右子树的高度差的绝对值不超过1
# 完全二叉树：如果一个二叉树除倒数第一层外都被填满，并且倒数第一层从左至右填充。
# 满二叉树： 如果一个二叉树的任意结点或者有0或者有2个孩子。
# 完美树：如果一个二叉树的所有层被填满。

# 堆
# 堆通常是一个可以被看做一棵树的数组对象。
# 堆是指程序运行时申请的动态内存，而栈只是指一种使用堆的方法(即先进后出)。
# 堆是由操作系统管理的一片空间,事先是没有在进程空间里分配的(比如你在没有分配堆的时候就访问堆空间会报一个内存访问错误),一般是由程序动态的分配出来,一旦分配了以后,一般需要程序去释放自己的堆空间.

# 堆的定义：1.是一个完全二叉树；2.上层的节点键值大于下层节点键值（最小堆），或者相反（最大堆）。
# 基于数组实现的堆
# 某节点位于完全数的i层，那么其左子节点位于数组2i位置，右子节点位于2i+1位，数组第一个位置未使用。

# 5、二叉树:
class Node:
    def __init__(self, data):
        self.data = data  # 数据域
        self.lchild = None  # 左子树
        self.rchild = None  # 右子树


class BTree:
    def __init__(self):
        self.root = None

    def add(self, data):
        # 往树中添加元素
        node = Node(data)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travel(self):
        # 广度遍历, 层序遍历
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.data, end=' ')
            if cur_node.lchild:
                queue.append(cur_node.lchild)
            if cur_node.rchild:
                queue.append(cur_node.rchild)

    def preoder(self, node):
        # 前序遍历：根–左–右
        if node is None:
            return
        print(node.data, end=' ')
        self.preoder(node.lchild)
        self.preoder(node.rchild)

    def inorder(self, node):
        # 中序遍历：左–根–右
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.data, end=' ')
        self.inorder(node.rchild)

    def postorder(self, node):
        # 后序遍历：左–右–根
        if node is None:
            return
        self.postorder(node.lchild)
        self.postorder(node.rchild)
        print(node.data, end=' ')


if __name__ == '__main__':
    tree = BTree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)

    tree.breadth_travel()
    print(' ')
    tree.preoder(tree.root)
    print(' ')
    tree.inorder(tree.root)
    print(' ')
    tree.postorder(tree.root)
